#include<bits/stdc++.h>
using namespace std;
void mergered(vector<int>& nums,int left,int mid,int right){
    int* temp= new int[left+mid+right];
    int le=left;
    int mi=mid+1;
    int k=0;
    while(le<=mid && mi<=right){
        if(nums[le]<nums[mi]){
            // cout<<le<<" ";
            temp[k++]=nums[le++];
        }
        else{
            // cout<<mi<<" ";
            temp[k++]=nums[mi++];
        }
    }
    while(le<=mid){
        temp[k++]=nums[le++];
    }
    while(mi<=right){
        temp[k++]=nums[mi++];
    }
    // cout<<k<<endl;
    for(int i=0;i<k;++i){
        nums[left+i]=temp[i];
    }
    delete temp;
}

void partiton(vector<int>& nums,int left,int right){
    if(left>=right){
        return;
    }
    int mid=left+(right-left)/2;
    partiton(nums,left,mid);
    partiton(nums,mid+1,right);
    // cout<<"test"<<endl;
    mergered(nums,left,mid,right);
}



int main(int argc, char const *argv[])
{
    
    vector<int> nums={1,2,6,8,7,1,6,1,2,3,5,4};
    partiton(nums,0,nums.size()-1);
    for(int i=0;i<12;++i){
        cout<<nums[i]<<" ";
    }
    cout<<endl;

    return 0;
}
